/*
 * @lc app=leetcode.cn id=37 lang=java
 *
 * [37] 解数独
 */

// @lc code=start
class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board);
    }

    public boolean dfs(char[][] board){
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                if(board[i][j]!='.') continue;
                for(char k='1';k<='9';k++){
                   if(isValid(board,i,j,k)){
                        board[i][j]=k;
                        if(dfs(board)){
                            return true;
                        }
                        board[i][j]='.';
                   }
                }
                return false;//9个数尝试完都没有满足条件的就可以结束了
            }
        }
        return true;
    }

    
    private boolean isValid(char[][] board, int i, int j, char k) {
        //同行
        for(int col=0;col<9;col++){
            if(board[i][col]==k){
                return false;
            }
        }
        //同列
        for(int row=0;row<9;row++){
            if(board[row][j]==k){
                return false;
            }
        }
        //同框
        //这里需要考虑定位，框左上角位置
        //实际上(i,j)会对应在行方向上第i/3个框，列方向第j/3个框
        //例如（0,3）对应行方向上第0(0/3)个框,列方向上第1(3/3)个框，框的最左上角即（0*3,1*3）
        int r=i/3*3;
        int c=j/3*3;
        for(int row=r;row<r+3;row++){
            for(int col=c;col<c+3;col++){
                if(board[row][col]==k){
                    return false;
                }
            }
        }
        return true;
    }
}
// @lc code=end

